import java.util.Arrays;
import java.util.PriorityQueue;

/**
* @description: 881. 救生艇
* @author hewei
* @date 2022/9/14 15:27
* @version 1.0
*/

public class NumRescueBoats {

    public int numRescueBoats1(int[] people, int limit) {
        PriorityQueue<Integer> heapMin = new PriorityQueue<>();
        PriorityQueue<Integer> heapMax = new PriorityQueue<>((a, b) -> b - a);
        for (int person : people) {
            heapMax.add(person);
            heapMin.add(person);
        }
        int n = people.length;
        int ans = 0;
        while (n > 0 && !heapMax.isEmpty()) {
            Integer max = heapMax.poll();
            Integer min = heapMin.peek();
            if (max + min <= limit && n >= 2) {
                n -= 2;
                heapMin.poll();
            } else --n;
            ++ans;
        }
        return ans;
    }

    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int l = 0;
        int r = people.length - 1;
        int ans = 0;
        while (l < r) {
            if (people[l] + people[r] <= limit) {
                ++l;
            }
            --r;
            ++ans;
        }
        if (l == r) ++ans;
        return ans;
    }
}
